package GreedyAlgorithmPackage;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Lzm
 * @version 1.0
 */
public class findMinArrowShots_ {
  @Test
  public void findMinArrowShots(){
    int[][] points = new int[][]{{-2147483646,-2147483645},{2147483646,2147483647}};
    //int[][] points = new int[][]{{10,16},{2,8},{1,6},{7,12}};
    Arrays.sort(points, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o2[0] - o1[0];
      }
    });
    for (int[] point : points) {
      StringBuilder sb = new StringBuilder();
      sb.append(point[0]).append(",").append(point[1]);
      System.out.println(sb.toString());
    }
    System.out.println(findMinArrowShots(points));
  }

  /**
   * @param points:
   * @return int
   * @author 25859
   * @description TODO
   * @date 2025/8/11 18:16
   * 重叠区间, 尽量让一个箭射爆气球
   */
  public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return Integer.compare(o1[0],o2[0]);
      }
    });
    int numberOfArrows = 1;
    for (int i = 1 ; i < points.length ;i++){
      if (points[i][0] > points[i-1][1]){
        // 气球i和气球i-1不挨着, 即区间不重叠
        numberOfArrows++;
        continue;
      }
      else {//气球i和气球i-1挨着, 有可能气球i的区间在气球i-1里面
        points[i][1] = Math.min(points[i][1], points[i - 1][1]);
      }
    }
    return numberOfArrows;
  }
}
